package com.zhanghp.class038;

/**
 * 复杂度： O(2^n)
 * <p>
 * 打印n层汉诺塔问题的最优移动轨迹
 * <p>
 * 最优步数解决：2^n - 1
 * <p>
 * f(n) = f(n - 1) + 1 + f(n - 1) = 2f(n-1) + 1<br/>
 * f(1) = 1
 * <ul>通项公式
 * <li>
 *     f(1) = 1
 * </li>
 * <li>
 *     f(2) = 2 + 1 = 3
 * </li>
 * <li>
 *     f(3) = 6 + 1 = 7
 * </li>
 * <li>
 *     f(4) = 14 + 1 = 15
 * </li>
 * <li>
 *     ....
 * </li>
 * </ul>
 * <p>
 *     每一项都是 2^n - 1<br/>
 *     设 f(k) = 2^k - 1<br/>
 *     f(1) 符合这个假设，那我们现在验证f(k+1)也符合<br/>
 *     由递推关系得，f(k+1) = 2f(k) + 1 <br/>
 *     f(k+1) = 2 * (2^k - 1) + 1<br/>
 *     得出 f(k + 1) = 2^(k + 1) - 1;<br/>
 *     进而得出f(n) = 2^n - 1
 * </p>
 *
 * @author zhanghp
 * @since 2024/6/20 17:17
 */
public class Code07_TowerOfHanoi {

    public static void main(String[] args) {
        hanoi(3);
    }

    public static void hanoi(int n){
        if (n > 0) {
            f(n, "左", "中", "右");
        }
    }

    public static void f(int n, String from ,String middle, String to){
        if (n == 1) {
            System.out.println(n + " " + from + " 到 " + to);
        }else {
            // 左（出发点） 中（中间） 右（终点）
            f(n - 1, from, to, middle);
            System.out.println(n + " " + from + " 到 " + to);
            // 左（出发点） 中（中间） 右（终点）
            f(n - 1, middle, from, to);
        }

    }

    public static void zuo(int i, String from, String to, String other) {
        if (i == 1) {
            System.out.println("移动圆盘 1 从 " + from + " 到 " + to);
        } else {
            // 左（出发点） 右（终点） 中（中间）
            zuo(i - 1, from, other, to);
            System.out.println("移动圆盘 " + i + " 从 " + from + " 到 " + to);
            // 左（出发点） 右（终点） 中（中间）
            zuo(i - 1, other, to, from);
        }
    }
}
